package linkedlist.other_1_quicksort;

public class QuickSort {
    public void quickSort(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        quickSort(head, null);
    }

    public void quickSort(ListNode lo, ListNode hi) {
        if (lo != hi && lo.next != hi) {
            ListNode pivotNode = paration(lo, hi);
            quickSort(lo, pivotNode);
            quickSort(pivotNode.next, hi);
        }
    }

    private ListNode paration(ListNode lo, ListNode hi) {
        int pivot = lo.val;
        ListNode mark = lo;
        ListNode cur = lo.next;
        while (cur != hi) {
            if (cur.val < pivot) {
                mark = mark.next;
                swap (mark, cur);
            }
            cur = cur.next;
        }
        swap(lo, mark);     // 3 2 1
        System.out.println("p : " + mark.val);
        return mark;
    }
    public void swap(ListNode l1, ListNode l2){
        int temp = l1.val;
        l1.val = l2.val;
        l2.val = temp;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        new QuickSort().quickSort(head);
        while(head != null){
            System.out.println(head.val);
            head = head.next;
        }
    }
}
